#ifndef SOLUTION_H_
#define SOLUTION_H_
#include <string>
#include <vector>
#include <cassert>
#include <cctype>
#include <sstream>
using namespace std;

class Solution 
{
public:
    string multiply(string num1, string num2)
	{
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
		if(num1.size()==0 || num2.size()==0)
			return "";
		
		size_t m = num1.size(), n = num2.size();
		vector<int> digits1(m), digits2(n);
		for(size_t i = 0;i<m;i++)
		{
			assert(isdigit(num1[i]));
			digits1[i] = num1[i]-'0';
		}
		for(size_t i=0;i<n;i++)
		{
			assert(isdigit(num2[i]));
			digits2[i] = num2[i]-'0';
		}

		vector<int> accu(n+m,0),curRow(m+1);
		for(size_t i=n-1;i!=-1;i--)
		{
			curRow[0] = 0;
			int carry = 0;
			for(size_t j=m-1;j!=-1;j--)
			{
				int cm = digits2[i]*digits1[j]+carry;
				curRow[j+1] = cm%10;
				carry = cm/10;
			}
			curRow[0] = carry;

			carry = 0;
			for(size_t j = m;j!=-1;j--)
			{
				int cm = accu[i+j]+carry+curRow[j];
				accu[i+j] = cm%10;
				carry = cm/10;
			}

			if(carry)
			{
				accu[i] = carry;
			}
		}


		size_t head;
		for(head = 0;head<accu.size();head++)
		{
			if(accu[head] != 0)
				break;
		}

		if(head == accu.size())
			return "0";

		string result(accu.size()-head,'0');
		for(size_t i=0;i<result.size();i++,head++)
			result[i] = '0'+accu[head];

		return result;

		
    }
};
#endif
